import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
/*
    static boolean[] checkCol;  //列
    static boolean[] dig1; //主对角线
    static boolean[] dig2; //副对角线
    static char[][] path;
    static List<List<String>> ret;
*/

/*
    public static List<List<String>> solveNQueens(int n) {
        checkCol = new boolean[n];
        dig1 = new boolean[2*n];
        dig2 = new boolean[2*n];
        path = new char[n][n];
        ret = new ArrayList<>();
        for(int i = 0;i < n;i++)
            Arrays.fill(path[i],'.');
        dfs(n,0);
        return ret;
    }

    public static void dfs(int n,int row) {  //row 行
        if(row == n) {
            List<String> tmp = new ArrayList<>();
            for(int i = 0;i < n;i++)
                tmp.add(new String(path[i]));
            ret.add(new ArrayList<>(tmp));
            return;
        }


        for(int col = 0;col < n;col++) {
            if(!checkCol[col] && !dig1[row-col+n] && !dig2[col+row]) {
                path[row][col] = 'Q';
                checkCol[col] = dig1[row-col+n] = dig2[col+row] = true;
                dfs(n,row+1);
                path[row][col] = '.';
                checkCol[col] = dig1[row-col+n] = dig2[col+row] = false;
            }
        }

    }
*/
/////////////////////////////////
    static char[][] path;
    static boolean[][] checkRow = new boolean[9][10];   //判断某行是否有某数
    static boolean[][] checkCol = new boolean[9][10];   //判断某列是否有某数
    static boolean[][][] grid = new boolean[3][3][10];  //判断某个数是否在3*3小方格

    public static boolean isValidSudoku(char[][] board) {
        path = board;
        return dfs(0);
    }

    public static boolean dfs(int row) {
        if(row == 9) return true;
        for(int col = 0;col < 9;col++) {
            int num = path[row][col];
            if(checkRow[row][num] || checkCol[col][num] || grid[row/3][col/3][num]) return false;
            else {
                checkRow[row][num] = checkCol[col][num] = grid[row/3][col/3][num] = true;
                if(!dfs(row+1)) return false;
                checkRow[row][num] = checkCol[col][num] = grid[row/3][col/3][num] = false;

            }

        }
        return true;
    }


    public static void main(String[] args) {

    }

}
